package qjc.m_堆;

import java.util.PriorityQueue;

public class m3_数据流的中位数 {
    /**
     * 大顶堆（存储较小的一半数字）,小顶堆（存储较大的一半数字）
     */
    PriorityQueue<Integer> right = new PriorityQueue<>();
    PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> Integer.compare(b, a));

    public m3_数据流的中位数() {
    }

    public void addNum(int num) {
        if (right.size() == left.size()) {
            right.offer(num);
            left.offer(right.poll());
        } else {
            left.offer(num);
            right.offer(left.poll());
        }
    }

    public double findMedian() {
        if (left.size() == right.size()) {
            return (left.peek() + right.peek()) / 2.0;
        } else {
            return left.peek();
        }
    }

}
